package LeetCodeQuestionBank;

/**
 * 977. 有序数组的平方
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [-4,-1,0,3,10]
 * 输出：[0,1,9,16,100]
 * 解释：平方后，数组变为 [16,1,0,9,100]
 * 排序后，数组变为 [0,1,9,16,100]
 * 示例 2：
 * <p>
 * 输入：nums = [-7,-3,2,3,11]
 * 输出：[4,9,9,49,121]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 104
 * -104 <= nums[i] <= 104
 * nums 已按 非递减顺序 排序
 */
public class T977 {
    public static void main(String[] args) {

        T977 t977 = new T977();
        int[] ints = t977.sortedSquares(new int[]{-5, -3, -2, -1});

    }

    public int[] sortedSquares(int[] nums) {

        //数组本身是有序 可以看成递增
        //两个指针从两头往中间靠近 每次都可以选出一个当前平方的最大值放入新数组中
        int[] sorted = new int[nums.length];

        //定义左右两个指针
        int left = 0;
        int right = nums.length - 1;
        //nums数组中大值为10^4 平方后不会溢出 int
        int leftSquared;
        int rightSquared;

        //当左右两个指针相遇 结束循环 此时都指向平方后最小的值  要求非递减  意思就是从小到大排列
        for (int i = nums.length - 1; i >= 0; i--) {
            //先更新一下指针 指向当前数的平方
            rightSquared = nums[right] * nums[right];
            leftSquared = nums[left] * nums[left];
            //那边大 说明他是当前数组平方后的最大值
            if (rightSquared > leftSquared) {
                sorted[i] = rightSquared;
                right = right - 1;
            } else {
                sorted[i] = leftSquared;
                left = left + 1;
            }

        }

        return sorted;

    }

}
